The present invention relates to methods and apparatus for securely generating a random number in one or more processors.
FIG. 1 illustrates an existing multiprocessing system 10 in which a plurality of processors 12A-D are coupled over a bus 14 and provide for series or parallel operation to achieve a processing objective. The multiprocessing system 10 may employ a random number generator (RNG) 16 within the system 10 that is used by all of the processors 12 requiring random number generation. Among the uses of the random number generator is to assist in creating a virtual private network (VPN) between the multiprocessor system 10 and an external system.
The problem with this manner of random number generation is that the multiprocessor system cannot host more than one user during the existence of the VPN without jeopardizing security. Indeed, without limiting access to the entire system 10, at least while the RNG 16 generates the random number, the random number could be intercepted, and the VPN would be susceptible to hacking. This severely limits the applications in which the system 10 may be employed.
Moreover, the randomness of the random number generated by the system described above is less than ideal. Limitations inherent in the hardware employed in such random number generators may cause the RNG 16 to have a tendency to generate either a disproportionate number and/or position of 1's or a disproportionate number and/or position of 0's.
Generally, a hardware circuit is coupled to an oscillator such as a ring oscillator which compares the voltage output value from the oscillator to a threshold voltage (Vth) provided by the hardware circuit. When the oscillator output voltage exceeds the threshold voltage, a logic 1 bit is generally output. Conversely, when the oscillator output voltage is lower than the threshold voltage, a logic 0 bit is generally output.
If the oscillator output voltage was exactly centered on Vth, and the hardware circuit voltage used for comparison to the oscillator voltage never strayed from Vth, a truly random stream of output bits could generated. However, due to semiconductor manufacturing process variations, noise, operating frequency variations, operating voltage variations, among other factors, the voltage output of the oscillator is generally not ideal, and therefore may not be centered on Vth. Moreover, due to non-idealities in the values of various circuit components, the threshold voltage Vth provided by the hardware circuit, used for comparison with the oscillator output voltage, may also depart from its ideal value. The consequence of such non-ideal behavior of both the oscillator and the hardware circuit may reduce the randomness of the ring oscillator 16 output.
FIG. 2 illustrates one example of non-ideal behavior of a ring oscillator. For the sake of simplicity, in this discussion, the graphs of the oscillator output 26A and 26B (collectively, 26) are assumed to be ideal. The ideal threshold voltage Vth 22 for the hardware circuit is shown essentially equidistant from the upper and lower boundaries of the graph which represent Vdd and Vss, respectively. If this ideal Vth 22 was used for comparison with the oscillator output, sampling of the oscillator output would generally lead to a random sequence of logical 1 bits and logical 0 bits in the ring oscillator output bit stream.
However, where the hardware circuit used for sampling the oscillator output 26 uses actual Vth 24, it is clear that the oscillator output 26 voltage would be greater than Vth 24 most of the time. Consequently, a sampling process that conducts a sequence of comparisons between oscillator output 26 and actual Vth 24 will lead to a output bit stream that is biased in favor of logical 1 bits, thereby defeating the desire to obtain a random distribution of bit values in the ring oscillator output bit stream. In the above, the randomness-defeating effect of a non-ideal hardware circuit threshold voltage Vth 24 was discussed. However, those of ordinary in skill in the art will recognize that non-ideal oscillator output voltage would also defeat the randomness of the output bit stream from ring oscillator 16.
Accordingly, there is a need in the art for a new approach to generating random numbers in a multiprocessing system which will enable: i) the generation of more randomized random numbers, ii) a system to simultaneously execute the programs of un-trusted entities, and/or iii) the creation of secure areas and communication links, the security of which will not be breached.